The present invention generally relates to scheduling multiple users sharing a communication resource, and particularly relates to scheduling shared use of the air interface in high data rate (HDR) wireless communication networks.
In some types of wireless communication networks, such as those configured in accordance with TIA/EIA/IS-856 standards, the forward link air interface is shared by a plurality of access terminals (users). At each time slot, or more generally, at each scheduling point, the network must decide which user or users to serve. This process of selecting users for service is generally referred to as “scheduling,” and the particular approach to scheduling adopted by a network determines at least in part several notable aspects of network operation. These aspects include overall network sector throughput, and the individual service rates of the users.
One existing approach, referred to as “proportional fair scheduling,” attempts, at each scheduling point, to serve the user having the largest ratio of requested service rate to average served rate. Thus, proportional fair scheduling selects the most underserved user relative to requested rate. Proportional fair schedulers, while well known, suffer significant limitations.
As an example, proportional fair scheduling does not accommodate differing quality-of-service requirements (QoS) between competing users, i.e., it does not consider maximum acceptable data delay constraints. Further, proportional fair scheduling does not support minimum service rates for users. On the other hand, proportional fair scheduling has several attractions.
First among these attractions are its relative simplicity and computational efficiency. As a gradient-based scheduling algorithm, proportional fair scheduling uses partial differentiation of the set of utility functions associated with the users being scheduled. Since each service hypothetical involves only one user at a time, partial differentiation with respect to the non-served users is simplified. Further, the gradient-based (steepest descent) approach to scheduling generally exhibits relatively fast convergence towards the optimum scheduling solution. Of course, because of the differentiability requirement, gradient-based scheduling does impose certain limitations on the flexibility of utility functions that may be assigned to users for evaluation by the scheduling algorithm.
Despite the attractions of proportional fair scheduling, its shortcomings are such that alternative scheduling approaches are needed. Approaches that begin accommodating QoS considerations include Largest Weighted Delay First (LWDF) and modified LWDF (M-LWDF) techniques that attempt to meet maximum packet delay requirements associated with desired QoS. However, at the least the LWDF approach effectively assumes constant channel capacity, and thus does not account for varying radio conditions across the set of users and over time.
User scheduling should accommodate minimum service rate considerations to insure that users having adequate radio conditions are served at or above minimum desired service rates. Where desired, such minimum-rate scheduling should further include QoS considerations, where scheduling biases include rate and delay considerations.